package com.year_23.april;

import java.util.ArrayList;
import java.util.List;

/**
 *  1026 节点与其祖先之间的最大值差
 *          https://leetcode.cn/problems/maximum-difference-between-node-and-ancestor/
 * @Author jsh
 * @Date 2023/4/18 22:05
 * @Version 1.0
 */
public class Day18 {
    public static void main(String[] args) {

    }

    public int maxAncestorDiff(TreeNode root){
        return dfs(root, root.val, root.val);
    }

    public int dfs(TreeNode root, int mi, int ma){
        if (root == null)return 0;
        int diff = Math.max(Math.abs(root.val - mi), Math.abs(root.val - ma));
        mi = Math.min(mi, root.val);
        ma = Math.max(ma, root.val);
        diff = Math.max(diff, dfs(root.left, mi, ma));
        diff = Math.max(diff, dfs(root.right, mi, ma));

        return diff;
    }

    /*
    *  94 二叉树的中序遍历
    *  https://leetcode.cn/problems/binary-tree-inorder-traversal/
    *
    *
    * */
    private List<Integer> list;
    public List<Integer> inorderTraversal(TreeNode root) {
        list = new ArrayList<Integer>();
        middleOrderTraversal(root);
        return list;
    }
    public void middleOrderTraversal(TreeNode root){
        if (root == null)return;
        middleOrderTraversal(root.left);
        list.add(root.val);
        middleOrderTraversal(root.right);
    }


    /*
    * 98 验证二叉搜索数
    * https://leetcode.cn/problems/validate-binary-search-tree/
    * */
    public boolean isValidBST(TreeNode root) {
        return isDfs(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    public boolean isDfs(TreeNode root, long mi, long ma){
        if (root == null)return true;
        if (root.val <= mi || root.val >= ma){
            return false;
        }
        return isDfs(root.left, mi, root.val) && isDfs(root.right, root.val, ma);
    }


}
class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(){}
    TreeNode(int val){
        this.val = val;
    }
    TreeNode(int val, TreeNode left, TreeNode right){
        this.val = val;
        this.left = left;
        this.right = right;
    }
}